package leetcode.method.dynamic_programming;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Program120MatrixMinimumTotal {

    public Program120MatrixMinimumTotal() {
    }
    public int minimumTotal(List<List<Integer>> triangle) {
        List<Integer> sum = new ArrayList<>();
        for (Integer i : triangle.get(0)) {
            sum.add(i);
        }
        List<Integer> tmp = null;
        for (int i = 1; i < triangle.size(); i++) {
            tmp = new ArrayList<>();
            for (int j = 0; j < triangle.get(i).size(); j++) {
                if (j == 0) {
                    tmp.add(sum.get(j) + triangle.get(i).get(j));
                } else if (j == triangle.get(i).size() - 1) {
                    tmp.add(sum.get(j - 1) + triangle.get(i).get(j));
                } else {
                    tmp.add(Math.min(sum.get(j),sum.get(j - 1)) + triangle.get(i).get(j));
                }
            }
            sum = tmp;
        }
        int res = Integer.MAX_VALUE;
        for (Integer i : sum) {
            res = Math.min(i, res);
        }
        return res;
    }

    public static void main(String[] args) {
        Program120MatrixMinimumTotal myStack = new Program120MatrixMinimumTotal();
        List<List<Integer>> triangle = new ArrayList<>();
        triangle.add(Arrays.asList(2));
        triangle.add(Arrays.asList(3,4));
        triangle.add(Arrays.asList(6,5,7));
        triangle.add(Arrays.asList(4,1,8,3));
        System.out.println(myStack.minimumTotal(triangle));
    }
}
